extern long treesort(long*, long, long, long*);
struct node_t {
	long value;
	struct node_t* left;
	struct node_t* right;
};
void initRandom(struct node_t nodes[], long length) {
	long l;
	srandom(12345);
	for (l=0; l<length; l++) {
		nodes[l].value = random();
		nodes[l].left = NULL;
		nodes[l].right = NULL;
	}
}
long ctraversetree(struct node_t* node, long dst[], long index) {
	if (node==NULL) return 0;
	long x = index;
	x+=ctraversetree(node->left,dst,x);
	dst[x]=node->value;
	x++;
	x+=ctraversetree(node->right,dst,x);
	return x-index;
}
void ctreeadd(struct node_t* node, struct node_t* new) {
	if (new->value>node->value) {
		if (node->right == NULL) {
			node->right = new;
		} else {
			ctreeadd(node->right,new);
		}
	} else {
		if (node->left == NULL) {
			node->left = new;
		} else {
			ctreeadd(node->left,new);
		}
	}
}
void cbuildtree(struct node_t data[], long length, long size) {
	long i;
	for (i = 1; i<length; i++) {
		ctreeadd(&data[0],&data[i]);
	}
}
void ctreesort(struct node_t data[], long length, long size, long dst[]) {
	cbuildtree(data,length,size);
	ctraversetree(data,dst,0);
}
#include <stdio.h>
#define SIZE 111
int test () {
	long errors=0;
	long i;
	struct node_t original[SIZE];
	struct node_t cimpl[SIZE];
	struct node_t aimpl[SIZE];
	initRandom(original,SIZE);
	for (i=0; i<SIZE; i++) {
		cimpl[i]=original[i];
		aimpl[i]=original[i];
	}
	long cres[SIZE];
	long ares[SIZE];
	ctreesort(cimpl,SIZE,sizeof(struct node_t),cres);
	treesort((long*)(aimpl),SIZE,sizeof(struct node_t),ares);
	long expected, result;
	for (i=0; i<SIZE; i++) {
		expected = cres[i];
		result = ares[i];
		if (result!=expected) {
			errors++;
			printf("Error: Index %d expected %ld but got %ld\n",i,expected,result);
		}
	} 
	if (errors==0) {
		return 1;
	} else {
		return 0;
	}
}

RET(test()==1);
